import java.util.LinkedList;

/***
 * This class manages how we explore the search space:
 * How to switch between different neighborhoods.
 *
 */
public class Search {
	public static final int NEXT_IMPROVEMENT = 1;
	public static final int BEST_IMPROVEMENT = 2;
	
	public static final int SWAP_HOME = 1;
	public static final int SWAP_TEAMS = 2;
	public static final int SWAP_ROUNDS = 3;
	public static final int SWAP_HALVES = 4;
	public static final int PLUS_ONE = 5;
	
	private int problemSize;
	private int currcost;
	
	private long start;
	
	// for storing some good solutions: 
	private Solution bestHardConstr;
	private Solution bestCosts;
	
	// use some kind of tabu lists (one for each neighborhood)
	private LinkedList<Integer> swapHomeTL = new LinkedList<Integer>();
	private int swapHomeTLSize = problemSize/2;
	private LinkedList<Integer> swapRoundsTL = new LinkedList<Integer>();
	private int swapRoundsTLSize = 1;//problemSize/2;
	private LinkedList<Integer> swapTeamsTL = new LinkedList<Integer>();
	private int swapTeamsTLSize = 1;//problemSize/4;
	
	/***
	 * This starts the search procedure with the given parameters. 
	 * @param improvementStrategy: NEXT_IMPROVEMENT, BEST_IMPROVEMENT
	 * @param iterations: the number of iterations in total
	 * @param iterationsbeforeSwitching: the number of iterations without 
	 * 		improvement before switching the neighborhood
	 * @param initialSolution: the initial solution that should be improved
	 * @param costPenalty: The cost penalty for one violated hard constraint.  
	 */
	public Search(int improvementStrategy, 
			int iterations, 
			Solution initialSolution,
			double costPenalty,
			int problemSize) {
		start = System.currentTimeMillis();
		// start the search procedure with the given parameters
		Solution currSol = initialSolution;
		this.problemSize = problemSize;
		this.swapHomeTLSize = 1; //problemSize/3; // TODO sizes maybe configurable?
		this.swapRoundsTLSize = 1; //problemSize/3;
		this.swapTeamsTLSize = 1; //problemSize/5;
		// TODO make this configurable:
		int[] neighborhoodOrdering = {SWAP_ROUNDS,SWAP_TEAMS,SWAP_HOME,SWAP_HALVES};
		Solution finalSolution = null;
		int i = 1;
		currcost = currSol.cost();
		System.out.println(currcost);
		while (true) {
			// iterations were not successful
			// after each iteration: 
			// store the solution if it is in any way the best
			currSol = oneNeighborhood(neighborhoodOrdering[0], improvementStrategy, currSol);
			storeIfGoodSolution(currSol);
			//currSol.output(true, false, true);
			//System.out.println("");
			currSol = oneNeighborhood(neighborhoodOrdering[1], improvementStrategy, currSol);
			storeIfGoodSolution(currSol);
			//currSol.output(true, false, true);
			//System.out.println("");
			currSol = oneNeighborhood(neighborhoodOrdering[2], improvementStrategy, currSol);
			storeIfGoodSolution(currSol);
			//currSol.output(true, false, true);
			//System.out.println("");
			currSol = oneNeighborhood(neighborhoodOrdering[3], improvementStrategy, currSol);
			storeIfGoodSolution(currSol);
			//currSol.output(true, false, true);
			//System.out.println("");
			// output the information of this one solution (i.e. costs and # of violated constraints
			if (System.currentTimeMillis()-start >= 300000) {
				break;
			} else {
				finalSolution = currSol;
			}
			i++;
		}
		System.out.println("\nFINAL SOLUTION:\n");
		finalSolution.output(true, true, true);
	}
	
	private Solution oneNeighborhood(int neighborhood, int improvementStrategy, 
			Solution currSol) {
		int oldcost = currSol.cost();
		Solution newSol = currSol.copy();
		while (true) {
			Solution tmpSol = oneSearchStep(neighborhood, improvementStrategy,
					newSol);
			if (tmpSol.cost() >= oldcost) {
				break;
			}
			oldcost = tmpSol.cost();
			newSol = tmpSol;
		}
		if (newSol.cost() < currcost) {
			System.out.println(newSol.cost() +" after Neighborhood "+neighborhood);
			//newSol.output(true, false, false);
			currcost = newSol.cost();
		}
		return newSol;
	}
	
	private Solution oneSearchStep(int neighborhood, int improvementStrategy, 
			Solution currSol) {
		Solution newSol = currSol.copy();
		if (neighborhood == SWAP_HOME) {
			Solution tmpSol;
			for (int i = 1; i < problemSize; i++) {
				// maintain the Tabu List:
				if (swapHomeTL.contains(i)) {
					continue;
				} else {
					if (swapHomeTL.size() >= swapHomeTLSize) {
						swapHomeTL.removeFirst();
					}
					swapHomeTL.add(i);
				}
				tmpSol = currSol.copy();
				tmpSol.swapHome(i);
				//System.out.println("TEST swapHome of Team "+i);
				if (acceptNewSolution(tmpSol, currSol)) {
					if (improvementStrategy == NEXT_IMPROVEMENT) {
						return tmpSol;
					} else if (improvementStrategy == BEST_IMPROVEMENT) {
						if (acceptNewSolution(tmpSol, newSol)) {
							newSol = tmpSol;
						}
					}
				}
			}
		} else if (neighborhood == SWAP_TEAMS) {
			int t1 = (int)(Math.random()*(problemSize-1))+1;
			while (swapTeamsTL.contains(t1)) {
				t1 = (int)(Math.random()*(problemSize-1))+1;
			}
			if (swapTeamsTL.size() >= swapTeamsTLSize) {
				swapTeamsTL.removeFirst();
			}
			swapTeamsTL.add(t1);
			for (int t2 = 0; t2 < problemSize; t2++) {
				if (t1 == t2) {
					continue;
				}
				Solution tmpSol = currSol.copy();
				// maintain the Tabu List:
				if (swapTeamsTL.contains(t2)) {
					continue;
				} else {
					if (swapTeamsTL.size() >= swapTeamsTLSize) {
						swapTeamsTL.removeFirst();
					}
					swapTeamsTL.add(t2);
				}
				tmpSol.swapTeams(t1, t2);
				//System.out.println("TEST swapTeam of "+t1+" and "+t2);
				if (acceptNewSolution(tmpSol, currSol)) {
					if (improvementStrategy == NEXT_IMPROVEMENT) {
						return tmpSol;
					} else if (improvementStrategy == BEST_IMPROVEMENT) {
						if (acceptNewSolution(tmpSol, newSol)) {
							newSol = tmpSol;
						}
					}
				}
			}
		} else if (neighborhood == SWAP_ROUNDS) {
			int rounds = (2*(problemSize-1));
			int r1 = (int)Math.random()*rounds;
			while (swapRoundsTL.contains(r1)) {
				r1 = (int)Math.random()*rounds;
			}
			if (swapRoundsTL.size() >= swapRoundsTLSize) {
				swapRoundsTL.removeFirst();
			}
			swapRoundsTL.add(r1);
			for (int r2 = 0; r2 < rounds; r2++) {
				if (r1 == r2) {
					continue;
				}
				Solution tmpSol = currSol.copy();
				// maintain the Tabu List:
				if (swapRoundsTL.contains(r2)) {
					continue;
				} else {
					if (swapRoundsTL.size() >= swapRoundsTLSize) {
						swapRoundsTL.removeFirst();
					}
					swapRoundsTL.add(r2);
				}
				tmpSol.swapRounds(r1, r2);
				//System.out.println("TEST swapRound of "+r1+" and "+r2);
				if (acceptNewSolution(tmpSol, currSol)) {
					if (improvementStrategy == NEXT_IMPROVEMENT) {
						return tmpSol;
					} else if (improvementStrategy == BEST_IMPROVEMENT) {
						if (acceptNewSolution(tmpSol, newSol)) {
							newSol = tmpSol;
						}
					}
				}
			}
		} else if (neighborhood == SWAP_HALVES) {
			int rounds = (2*(problemSize-1));
			//int cut = (int)(Math.random()*rounds);
			for (int i = 1; i < rounds; i++) {
				Solution tmpSol = currSol.copy();
				tmpSol.swapHalves(i);
				if (acceptNewSolution(tmpSol, currSol)) {
					if (improvementStrategy == NEXT_IMPROVEMENT) {
						return tmpSol;
					} else if (improvementStrategy == BEST_IMPROVEMENT) {
						if (acceptNewSolution(tmpSol, newSol)) {
							newSol = tmpSol;
						}
					}
				}
			}
		} else if (neighborhood == PLUS_ONE) {
			Solution tmpSol = currSol.copy();
			tmpSol.plusOne();
			if (acceptNewSolution(tmpSol, currSol)) {
				if (improvementStrategy == NEXT_IMPROVEMENT) {
					return tmpSol;
				} else if (improvementStrategy == BEST_IMPROVEMENT) {
					if (acceptNewSolution(tmpSol, newSol)) {
						newSol = tmpSol;
					}
				}
			}
		}
		return newSol;
	}
	
	private boolean acceptNewSolution(Solution newSol, Solution oldSol) {
		boolean result = false;
		if (newSol.evaluate() > oldSol.evaluate()) {
			result = false;
		} else if (newSol.cost() <= oldSol.cost()) {
			result = true;
		} else {
			result = false;
		}
		/*if (result) {
			System.out.println("chosen new "+newSol.cost()+"/"+newSol.evaluate()+
					" over old "+oldSol.cost()+"/"+oldSol.evaluate());
		} else {
			System.out.println("chosen old "+oldSol.cost()+"/"+oldSol.evaluate()+
					" over new "+newSol.cost()+"/"+newSol.evaluate());
		}*/
		return result;
	}
	
	private void storeIfGoodSolution(Solution candidate) {
		if (bestHardConstr == null)
			bestHardConstr = candidate;
		if (bestCosts == null)
			bestCosts = candidate;
		
		if (candidate.evaluate() < bestHardConstr.evaluate()) {
			bestHardConstr = candidate;
		}
		if (candidate.cost() < bestCosts.cost()) {
			bestCosts = candidate;
		}
	}
}
